from typing import List


class Solution:
    def scoreOfStudents(self, s: str, answers: List[int]) -> int:
        # ---------- 计算正确答案 ----------
        correct = eval(s)

        # ---------- 计算所有可能的错误答案 ----------
        groups = s.split("*")
        groups_maybe = [[] for _ in range(len(groups))]
        print("根据乘号分段:", groups)

        for i, group in enumerate(groups):
            plus_num = len(group) // 2  # 计算段落中的加号数量

            # ---------- 处理只有一个数的段落 ----------
            if plus_num == 0:
                groups_maybe[i].append(group)
                continue

            # ---------- 处理有加号的段落 ----------
            group_nums = [int(group[i]) for i in range(0, len(group), 2)]
            # print(group_nums, plus_num)
            for stat in range(1 << plus_num):  # 遍历所有保留加号的方案
                now = [group_nums[0]]
                for j in range(plus_num):
                    if stat & (1 << j):  # 这个加号保留
                        now.append(group_nums[j + 1])
                    else:  # 这个加号不保留
                        now[-1] += group_nums[j + 1]
                now_str = "+".join([str(num) for num in now])
                groups_maybe[i].append(now_str)
                # print(groups[i], "->", plus_num, "->", stat, "->", now, "->", now_str)

        print("所有可能的错误答案组合:", groups_maybe)

        # ---------- 深度优先搜索计算所有可能的错误答案 ----------
        wrong = set()

        def dfs(ii, now_res):  # ii=当前段落下标,之前的结果
            if ii == len(groups):
                wrong.add(eval("*".join(now_res)))
            else:
                for jj in range(len(groups_maybe[ii])):
                    now_res.append(groups_maybe[ii][jj])
                    dfs(ii + 1, now_res)
                    now_res.pop()

        dfs(0, [])

        print("所有错误答案:", wrong)

        # ---------- 计算最终结果 ----------
        ans = 0
        for answer in answers:
            if answer == correct:
                ans += 5
            elif answer in wrong:
                ans += 2
        return ans


if __name__ == "__main__":
    print(Solution().scoreOfStudents(s="7+3*1*2", answers=[20, 13, 42]))  # 7
    print(Solution().scoreOfStudents(s="3+5*2", answers=[13, 0, 10, 13, 13, 16, 16]))  # 19
    print(Solution().scoreOfStudents(s="6+0*1", answers=[12, 9, 6, 4, 8, 6]))  # 10

    # 测试用例 27/274
    print(Solution().scoreOfStudents(s="1+2*3+4", answers=[13, 21, 11, 15]))  # 11

    # 测试用例 29/274  预期: 122
    print(Solution().scoreOfStudents(s="4+2*2+3*1+2",
                                     answers=[42, 17, 13, 66, 32, 547, 21, 90, 13, 33, 45, 66, 34, 21, 13, 13, 13, 46,
                                              21, 177, 18, 13, 18, 16, 16, 678, 13, 42, 66, 13, 18, 18, 777, 21, 924,
                                              13, 268, 13, 13, 13, 25, 62, 45, 33, 888, 779, 13, 206, 48, 13, 34, 17]))
